package com.zhanghp.class04;

import java.util.HashSet;

/**
 * <h1>位图实现</h1>
 * <a href = "https://blog.csdn.net/dilireba666/article/details/130419554">bitMap简介</a>
 * <p>很显然，使用 BitMap 存储这个数组只使用了使用15bit，而使用 HashSet 或 HashMap 的话，
 * 一个数组元素会存储为一个int，而一个int占4个byte，即4*8=32bit，这里有5个数组元素则需要5*32=160bit，这样的话，
 * 使用 BitMap 存储一个元素则可以节省32倍的内存空间。因此，BitMap 的优势就不言而喻了。</p>
 * <hr/>
 *
 * <h2>n % 2^k = n & (2^k -1)原因</h2>
 * <ul>
 * n mod 2^k ,只要找到整数r，使得 r∈[0,2^k)，并且n = q * 2^k + r
 *     <li>q：整数商</li>
 *     <li>r：余数</li>
 * </ul>
 *
 * @author zhanghp
 * @since 2023/10/25 9:47
 */
public class Code01_BitMap {

    public static void main(String[] args) {
        System.out.println("测试开始！");
        int max = 10000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        int testTime = 10000000;
        for (int i = 0; i < testTime; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.333) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.666) {
                bitMap.delete(num);
                set.remove(num);
            } else {
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("Oops!");
                    break;
                }
            }
        }
        for (int num = 0; num <= max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }

    public static class BitMap{
        private final long[] bits;

        public BitMap(int max){
            // 加64原因，（如果max传的数值小于64，不加64，则会有问题）
            bits = new long[(max + 64) >> 6];
        }

        public void add(int a){
            // 1L原因，如果是1，则为int，int是32字节，如果移位超出32，则会出问题
            bits[a >> 6] |= 1L << (a & 63);
        }

        public void delete(int a){
            bits[a >> 6] &= ~(1L << (a & 63));
        }

        public boolean contains(int a){
            // 有0则为0
            return  (bits[a >> 6] & (1L << (a & 63))) != 0;
        }
    }
}
